В 1752 г. была заложена крепость Святых Петра и Павла (с 1807 город Петропавловск), в 1766 г. в крепости возведена деревянная Петропавловская ц. Собор во имя первоверховных апостолов Петра и Павла заложен в 1803 г., в 1812 г. полностью разобран, 22 окт. 1813 г. на том же месте заложен каменный 3-престольный храм. Главный придел, во имя апостолов Петра и Павла, освящен в 1815 г., северный - во имя свт. Николая Чудотворца - в 1818 г., юж. придел, в честь Покрова Пресв. Богородицы,- в 1821 г. В 1838 г. от пожара пострадала колокольня, новая возведена в 1848 г.
Всехсвятская ц. в Петропавловске заложена как кладбищенская в 1890 г., освящена в 1894 г. Церковь строилась силами городских властей на средства петропавловского купца С. И. Хлебникова и его супруги, А. Д. Хлебниковой. Возведение храма благословил прот. прав. Иоанн Кронштадтский.
На территории П. и Б. е. с 1918 по 1940 г. пострадали за Христа 52 чел., большая часть из них - священнослужители. С территорией епархии связаны жизнь и служение епископов священномучеников Мефодия (Краснопёрова) и Иоанна (Троянского), прот. сщмч. Михаила Мякишева, священников священномучеников Владимира Панькина, Афанасия Милова, Василия Бовы, протодиак. сщмч. Иоанна Яковлевича Смирнова.
16 окт. 1938 г. горсовет принял решение о закрытии Петропавловской ц. и об использовании ее для хозяйственных нужд. Кладбищенская Всехсвятская ц. в Петропавловске - единственный храм в городе и 2-й в области, к-рый не закрывался в советское время (в 1961, 1968 и 1973 власти предпринимали попытки закрыть этот храм). В 1954-1978 гг. настоятелем Всехсвятской ц. служил прот. Сергий Ногачевский (1896-1978).
В 1946 г. облисполком постановил передать верующим Петропавловский собор, к 1952 г. он был полностью восстановлен. После возвращения Петропавловского собора в советский период в Северо-Казахстанской обл. не было открыто или передано верующим ни одного храма.
14 марта 1957 г. Петропавловское вик-ство было упразднено, викарный Петропавловский еп. Иосиф (Чернов; с 25 февр. 1958 архиепископ, впосл. митрополит) поставлен во главе самостоятельной Петропавловской и Кустанайской епархии, в состав к-рой входили Северо-Казахстанская, Акмолинская, Карагандинская, Кокчетавская и Кустанайская области КазССР. С переводом архиеп. Иосифа 15 сент. 1960 г. на Алма-Атинскую кафедру Петропавловская и Кустанайская епархия была упразднена, ее территория вошла в состав объединенной Алма-Атинской и Казахстанской епархии.
31 янв. 1991 г. территория П. и Б. е. вошла в состав Чимкентской и Акмолинской епархии. Согласно решению Синода от 6 окт. 2010 г., из состава Чимкентской была выделена Костанайская и Петропавловская епархия, 5 окт. 2011 г. П. и Б. е. получила самостоятельность.
В 1997 г. при Петропавловской ц. освящен крестильный храм в честь праздника Св. Пятидесятницы. Вознесенский кафедральный собор в Петропавловске был заложен как приходская церковь 20 мая 1999 г. в память о разрушенном в советское время одноименном соборе. 26 нояб. 2005 г. храм освящен архиеп. Чимкентским и Акмолинским Елевферием (Козорезом). После образования П. и Б. е. в 2011 г. Вознесенский храм получил статус кафедрального собора.
При образовании П. и Б. е. 5 окт. 2011 г. на Петропавловскую кафедру был назначен Магаданский еп. Гурий (Шалимов). 30 мая 2014 г. еп. Гурий был почислен на покой по состоянию здоровья, с того же года епархией управляет еп. Владимир (Михейкин).
17 апр. 2013 г. в епархиальном центре заложена ц. во имя сщмч. Мефодия, еп. Петропавловского; 29 янв. 2015 г. храм освящен. 3 июня 2016 г. в Петропавловске состоялась закладка ц. во имя прп. Севастиана Карагандинского; освящение церкви состоялось 18 нояб. 2018 г.
В Петропавловске с 1995 г. работает единственная в Казахстане средняя общеобразовательная епархиальная школа во имя прп. Сергия Радонежского. В пределах епархии действуют 22 церковноприходские школы с б-ками при них. При Всехсвятской ц. в Петропавловске есть крестильный храм во имя прав. Иоанна Кронштадтского, действуют епархиальный музей и древлехранилище. Ежегодно в дек. проходят Свято-Мефодиевские епархиальные образовательные чтения.
С 1994 г. в день памяти первоверховных апостолов Петра и Павла - покровителей г. Петропавловска совершается крестный ход по центральным улицам обл. центра. 31 июля по храмам Кызылжарского р-на Северо-Казахстанской обл. следует крестный ход с чтимым списком Абалакской иконы Божией Матери «Знамение» в память о посещении Петропавловского у. цесаревичем Николаем (см. ст. Николай II Александрович, мч., имп.) в 1891 г.
Архиеп. Иосиф (Чернов; 14 марта 1957 - 15 сент. 1960; до 25 февр. 1958 в сане епископа), еп. Гурий (Шалимов; 5 окт. 2011 - 30 мая 2014), еп. Владимир (Михейкин; с 8 июня 2014 по наст. время).
Всехсвятский (женский, в Петропавловске; основан в 1908 при кладбищенской Всехсвятской ц., после 1917 существовал как Никольская трудовая артель, в 1940 некоторые монахини еще проживали при храме), во имя арх. Михаила (женский, близ с. Пресноредуть Жамбылского р-на; основан в 1896 как жен. община (офиц. учреждена Синодом в 1901), с 1908 мон-рь, закрыт в 1921).